/*
 * @lc app=leetcode.cn id=494 lang=java
 *
 * [494] 目标和
 *
 * https://leetcode-cn.com/problems/target-sum/description/
 *
 * algorithms
 * Medium (42.20%)
 * Likes:    166
 * Dislikes: 0
 * Total Accepted:    13.7K
 * Total Submissions: 32.2K
 * Testcase Example:  '[1,1,1,1,1]\n3'
 *
 * 给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或
 * -中选择一个符号添加在前面。
 *
 * 返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
 *
 * 示例 1:
 *
 * 输入: nums: [1, 1, 1, 1, 1], S: 3
 * 输出: 5
 * 解释:
 *
 * -1+1+1+1+1 = 3
 * +1-1+1+1+1 = 3
 * +1+1-1+1+1 = 3
 * +1+1+1-1+1 = 3
 * +1+1+1+1-1 = 3
 *
 * 一共有5种方法让最终目标和为3。
 *
 *
 * 注意:
 *
 *
 * 数组非空，且长度不会超过20。
 * 初始的数组的和不会超过1000。
 * 保证返回的最终结果能被32位整数存下。
 *
 *
 */

// @lc code=start
class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        int sum = 0;
        for(int a : nums) {
            sum += a;
        }
        int dp[][] = new int[nums.length][sum << 1 + 1];
        dp[0][sum+1 - nums[0]] = 1;dp[0][sum+1 + nums[0]] = 1;
        for(int i=1; i<nums.length; i++) {
            for(int j=0; j < dp[0].length; j++) {
                if(sum+1 + j-nums[i] > -1)
                    dp[i][j] += dp[i-1][sum+1 + j-nums[i]];
                if(sum+1 + j+nums[i] > -1)
                    dp[i][j] += dp[i-1][sum+1 + j+nums[i]];
            }
        }
        return dp[nums.length-1][S+sum];
    }
}
// @lc code=end

